perm filename AGRE.REV[1,JRA] blob
sn#424662 filedate 1979-03-08 generic text, type C, neo UTF8
COMMENT ā VALID 00005 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002
C00011 00003 (DEF INDEX (FN LST)
C00013 00004 p33 -----BOTTOM -------------------
C00015 00005 --p 13 bottom ----------------------
C00018 ENDMK
Cā;
This paper discusses the manner in which functions are defined and
manipulated in various dialects of LISP. Though LISP DOES allow
functional objects, we argue that typical implementations of LISP restrict
their use unnecessarily either by supplying weak definitional mechanisms
or by supporting only partial implementations of the concept. We present a
general implementation mechanism which allows greater uniformity in the
handling of different types of functions.
Since few languages support functional objects, being deficient either in
expressibility within the language or deficient in their implementation,
programmers tend not to realize the power of functions as objects.
Therefore we begin by exploring how programming styles might be affected
by the availablity of a "theoretically sound" implementation of functions.
A common sort of function in LISP takes a function and a list as arguments
and applies the function several times to different parts of the list,
returning a list of the results. For example %3maxlist%1 on page ****
does this. We want to generalize this behavior. To do so it is convenient
to refer to constant functions as objects without giving them explicit
names just as we talk about the list (A B C) as an explicit constant
without naming it x or y. Function constants are a bit more complex: they
may take parameters. This is not a contradiction: the "binary sum
function" is a constant function; it always produces the sum of its
arguments regardless of the name we might attach to it.
(DEF FOO (X Y)(PLUS X Y)) and (DEF BAR (U V)(PLUS U V))) denote the same
function; the names FOO and BAR are as irrelevant as the variable names X,
Y and U , V. In LISP we represent this independence of naming by the
lambda notation, writing the sum function as (LAMBDA (X Y)(PLUS X Y)); if
you don't like "LAMBDA", think "PROCEDURE". We want these LAMBDA (or
PROCEDURE) objects to be "first class" objects, freely manipulable by
LISP, passed as arguments and returned as values. Actually we have been
usinf functional objects and lambda expressions already. The effect of
(DEF <name> <parameters> <body>) was to associate a functional object with
<name>, where the functional object was (LAMBDA <parameters> <body>).
(DEF <name> <parameters> <body>) is an abbreviation for
(LET <name> (LAMBDA <parameters> <body>)). We will use this LET notation
in a few moments.
As an example of how to apply these notions suppose we wish to define a
function which takes a list of integers as its argument and makes a new
list each of whose elements is double the corresponding element of the
original list.
(DOUBLE_EM '(9 2 7 4 5)) is (18 4 7 8 10)
Thus we want to apply the "doubling function to each element of the list.
Instead of naming the function, we just give it as an explicit
lambda expression (LAMBDA (X)(PLUS X X)), and we apply it using
a general "mapping function"
called MAPFIRST which takes as its arguments a function and a list and
applies the function to each element of the list, returning a list of the
results.
(DEF MAPFIRST (FN LST)
(COND((NULL LST) ())
(T (CONCAT(FN (FIRST LST))
(MAPFIRST FN (REST LST))))))
and
(DEF DOUBLE_EM (L) (MAPFIRST (LAMBDA (X)(PLUS X X))
L))
Further, suppose that we would rather have a doubling function which would
take an arbitrary number of arguments (like LIST), writing (DOUBLE_IT 9 2
7 4 5) or (DOUBLE_IT 2 6). To cater to this extension, we will allow the
parameter lists of LAMBDA's and DEF's to be atomic as well as lists. An
atomic parameter "list" will signify our intention to associate the list
of evaluated actual parameters with that atom. Thus LIST could be defined
as (DEF LIST A A). It is a more pleasing notation, but of course will
have to be supported in our implementation.
now suppose that we want a function named VECTORIZE such that (VECTORIZE
<fn>) returned a function which would take a number of arguments and apply
<fn> to each one, returning a list of values obtained. Notice that we
expect the value of VECTORIZE itself to be a function. For example a
function LISTIFY which was to apply the LIST function to each of its
arguments:
(LISTIFY 'A 'B 'C) would give ((A) (B) (C)).
could now be defined as:
(DEF LISTIFY LST ((VECTORIZE LIST) LST)
where we are using the new parameter list syntax.
Notice that LISTIFY is the same as (LAMBDA ARGS (MAPFIRST LIST ARGS).
This gives us a hint that VECTORIZE must be something like:
(DEF VECTORIZE (FN) (LAMBDA ARGS (MAPFIRST FN ARGS)))
since a call on %3VECTORIZE%1 will bind the actual parameter (a function)
to the name FN, and should return the functional lambda-expression as
value. This definition is almost correct; however, as we pass the
function out as value, we must assure that the binding to FN be
maintained. LISP dialects have two mechanisms to affect this: the
FUNCTION construct and the CLOSURE construct. For our present example
these constructs are identical. Later we will se that CLOSURE will give
finer control over the binding process. For now we will use:
(DEF VECTORIZE (FN) (CLOSURE '(FN)
(LAMBDA ARGS (MAPFIRST FN ARGS))))
where the first argument to CLOSURE is the list of variables we want
"trapped" to their current bindings.
(DEF INDEX (FN LST)
(COND ((NULL (REST LST) (FIRST LST))
(T (FN (FIRST LST)
(INDEX FN (REST LST))))))
(DEF INDEXIFY (FN)
(CLOSURE '(FN)
(LAMBDA ARGS (INDEX FN ARGS))))
This sort of definition has considerable potential for inproving the
readibility of code. Now one need only write the 2-argument version of any
desired function and then apply INDEXIFY to it. For example a general
minimization function MIN, such that (MIN 2 5 1 5) gives 1, could be
defined as the "indexification" of the binary minimization function.
that is (INDEXIFY (LAMBDA (X Y)(COND ((LESS X Y) X)
(T Y))))
The association of names with such functional objects requires requires
the LET notation since this object already contains an embedded parameter
list.
(LET MIN (INDEXIFY
(LAMBDA (X Y)(COND ((LESSP X Y) X)
(T Y)))))
With MIN we have an example of an explicity constructed functional object.
p33 -----BOTTOM -------------------
This problem is not the sole province of LISP; it is a problem intimately
connected with the scoping rules which a language chooses. The two general
disciplines are static (or lexical) scope and dynamic scope. Static scope,
present in most ALGOL-like languages, associates values with names at the
time the object is created. For example:
(LET F (LAMBDA(N) (TIMES N N)))
and then
(LET F
(LAMBDA (N)
(COND ((LESSP N 2) 1)
(T (TIMES N
(F (SUB1 N))))))
(F 6) would give 12 since the inner F would be bound to the earlier
definition.
The default binding in LISP is dynamic, meaning that the value associated
with a name is determined at the time the object is referenced. Thus LISP
gets the expected answer 6 in the previous example; but as we have just
seen, dynamic binding can also give erroneous resluts. Most languages
finesse the problem by severly restricting the use of functional objects;
LISP does try to solve it.
--p 13 bottom ----------------------
The pseudo-code to be presented below shows how these functins and their
expansion routines might be implemented on a standard machine. We will
remain machine independent to the extent that the presentation will not
suffer. That is, the decription will have a strong imperative flavor
immediately translatable into sequences of machine code, yet we will not
commit ourself to a specific machine architecture. For the purpose of these
discussions, let us make some defining assumptions.
1. We will describe the implementation in terms of specific representation
of symbol tables as linked bocks of parameter bindings.
With this implementation comes a search mechanism for locating the value
of a variable. This basic strategy is called "deep binding"; its essential
characteris is that the table is organized by "environment" and the search
mechanism traverses these environments looking for the first occurrence of
the variable name. An alternative strategy, called "shallow binding",
orgainzes the table by variable name, associating with each variable the
list of possible binding. In this case the lookup routine has an easier
time of finding the name, but perhaps a more difficult time in extracting
the value. Both schemes are used extensively in LISP; both have simplifying
subcases; both have difficulties.
---bottom p14 ----------------------
We will also assume a collection of "internal machine registers" which
will will appear as global variable in our code fragments. Though our
code could be describe in M-LISP notation, we use an ALGOL-like dialect to
reinforce the low level implementation flavor of the endeavor.